package src.dp.sequence;

public class no392 {//判断子序列

    //和最长公共子序列一样，只是最后加一个判断，如果s是t的子串，那s本身一定是最长的子序列
    public boolean isSubsequence(String s, String t) {
        int len1 = s.length();//s子串
        int len2 = t.length();//t更长的串
        int[][] dp = new int[len1 + 1][len2 + 1];

        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                //i、j遍历时，比较的是i-1 和 j-1 位置的字母
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    //当前元素不相等时，就维护之前的最大状态
                    dp[i][j] = dp[i][j - 1];
                }
            }
        }
        return dp[len1][len2] == s.length();

    }

    //法2：双指针
    public boolean isSubsequence2(String s, String t) {
        if (s.isEmpty()) return true;
        int len1 = s.length();
        int len2 = t.length();
        int i = 0, j = 0;  //i遍历s，j遍历t
        while (i < len1 && j < len2) {
            if (s.charAt(i) == t.charAt(j)) {
                i++;
                j++;
            } else j++;
            //判断如果 i 已经移到s串的末尾了，则是子串 (不管t是否在末尾)
            if (i == len1) {
                return true;
            }
        }
        return false;
    }

    //dp法，状态压缩
    public boolean isSubsequence3(String s, String t) {
        int[] dp = new int[s.length() + 1];
        for (int i = 0; i < t.length(); i ++) {
            // 需要使用上一轮的dp[j - 1]，所以使用倒序遍历
            for (int j = dp.length - 1; j > 0; j --) {
                // i遍历的是t字符串，j遍历的是dp数组，dp数组的长度比s的大1，因此需要减1。
                if (t.charAt(i) == s.charAt(j - 1)) {
                    dp[j] = dp[j - 1] + 1;
                }
            }
        }
        return dp[s.length()] == s.length();
    }
}
